//
//  BinaryTreeNode.swift
//  StringForSwift
//
//  Created by DeLong Yang on 2017/7/27.
//  Copyright © 2017年 YiXue. All rights reserved.
/*
    2017 - 7- 27 
    笔者实验：http://www.cnblogs.com/manji/p/4903990.html 实际并非如此 而是有 问题
    笔者认为 有必要使用OC 对比一边  发现OC上 是好的 swift 里面形式参数等的更改其实并不好
 
 */

import UIKit

class BinaryTreeNode: NSObject {
    
    var value:Int  = 0
    var leftNode:BinaryTreeNode?;  // 有可能 左边节点啥都没有
    var rightNode:BinaryTreeNode?; // 很有可能也没有 右边的节点
    
    init(value_:Int,leftNode_:BinaryTreeNode?,rightNode_:BinaryTreeNode?) {
       value = value_
       leftNode = leftNode_
       rightNode = rightNode_
    }
    
    convenience override init() {
        let leftNode = BinaryTreeNode(value_: 0, leftNode_: nil, rightNode_: nil)
        let rightNode = BinaryTreeNode(value_: 0, leftNode_: nil, rightNode_: nil)
        self.init(value_: 0, leftNode_: leftNode, rightNode_: rightNode)
        
    }
    
    //  MARK  create a treeNode
    //  一定会返回 一个treeNode 如果没有会新建一个Node。个人感觉这是 作者在乱写 在 打出来的结构中发现好多元素少了 只有右边的元素
    class func addTreeNode( treeNode:inout BinaryTreeNode, value:Int) -> BinaryTreeNode {
        if treeNode == nil {
            treeNode = BinaryTreeNode()
            treeNode.value = value
            return treeNode
        }else if (value <= (treeNode.value)){
            print("to left");
            //值小于根节点，则插入到左子树
            treeNode.leftNode = BinaryTreeNode.addTreeNode(treeNode: &treeNode.leftNode!, value: value)
         
            return treeNode
        }else{
            
            
            print("to right")
            treeNode.rightNode = BinaryTreeNode.addTreeNode(treeNode: &treeNode.rightNode!, value: value)
            return treeNode
        }
    }
    
    //  创建一个 整个的 nodesTree   其实tree 也是 一个node 因为 其 leftNode and rightNode have Value 于是成为一个串起来的 tree
    class func  createTreeWith(values:Array<Int>) -> BinaryTreeNode{
        
        var root:BinaryTreeNode?
        
        for index in values{
            root = BinaryTreeNode.addTreeNode(treeNode: &root!, value: index)
        }
        
        return root!
    }
    
    // get node in tree  at index could be nil
    class func treeNodeAt(index:Int ,inTree:BinaryTreeNode?) -> BinaryTreeNode?{
        if inTree == nil || index<0 {
            return nil
        }else{
            
            // 一定不为 nil treeNode
            let queueArray:NSMutableArray = NSMutableArray()
            queueArray.add(inTree!)
            var count = index
            
            while queueArray.count>0 {
                let node = queueArray.firstObject as! BinaryTreeNode
                if count == 0{
                    return node
                }
                
                //
                queueArray.remove(0)
                count -= 1
                
                if (node.leftNode != nil) {
                    queueArray.add(node.leftNode!)
                }
                
                if node.rightNode != nil {
                    queueArray.add(node.rightNode!)
                }
                
            }
            
            return nil
        }
    }
    
    
}





















